Private information retrieval (PIR) is the problem of retrieving asefficiently as possible, one out of $K$ messages from $N$ non-communicatingreplicated databases (each holds all $K$ messages) while keeping the identityof the desired message index a secret from each individual database. Theinformation theoretic capacity of PIR (equivalently, the reciprocal of minimumdownload cost) is the maximum number of bits of desired information that can beprivately retrieved per bit of downloaded information. $T$-private PIR is ageneralization of PIR to include the requirement that even if any $T$ of the$N$ databases collude, the identity of the retrieved message remains completelyunknown to them. Robust PIR is another generalization that refers to thescenario where we have $M \geq N$ databases, out of which any $M - N$ may failto respond. For $K$ messages and $M\geq N$ databases out of which at least some$N$ must respond, we show that the capacity of $T$-private and Robust PIR is$\left(1+T/N+T^2/N^2+\cdots+T^{K-1}/N^{K-1}\right)^{-1}$. The result includesas special cases the capacity of PIR without robustness ($M=N$) or $T$-privacyconstraints ($T=1$).
展开▼
机译：私有信息检索（PIR）的问题是尽可能低效率地从$ N $个非通信复制数据库（每个保存所有$ K $消息）中的$ K $消息中检索一个，同时保持所需消息索引的身份保密每个单独的数据库。 PIR的信息理论容量（相当于最小下载成本的倒数）是每位下载信息可以私下检索的所需信息的最大位数。 $ T $ -private PIR是对PIR的概括，它包含以下要求：即使$ N $数据库中的任何$ T $相互勾结，检索到的消息的身份也对他们完全未知。健壮的PIR是另一种概括，它指的是我们拥有$ M \ geq N $个数据库的情况，其中任何$ M-N $都可能无法响应。对于$ K $消息和$ M \ geq N $数据库（其中至少一些$ N $必须响应），我们显示$ T $ -private和Robust PIR的容量为$ \ left（1 + T / N + T ^ 2 / N ^ 2 + \ cdots + T ^ {K-1} / N ^ {K-1} \ right）^ {-1} $。作为特殊情况，结果包括没有健壮性（$ M = N $）或$ T $ -privacyconstraints（$ T = 1 $）的PIR容量。
展开▼
